package leetcode;

import util.Tree;
import util.TreeNode;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0114.java
 * @Author : WangRuoyu
 * @Date 2023/11/27 22:15
 */

public class Q0114 {
    //    private TreeNode dfs(TreeNode root) {
//        if (root.left == null && root.right == null) {
//            return root;
//        } else if (root.right == null) {
//            root.right = root.left;
//            root.left = null;
//            return dfs(root.right);
//        } else if (root.left == null) {
//            return dfs(root.right);
//        } else {
//            TreeNode tmp = root.right;
//            root.right = root.left;
//            root.left = null;
//            TreeNode p = dfs(root.right);
//            p.right = tmp;
//            return dfs(tmp);
//        }
//    }
//
//    public void flatten(TreeNode root) {
//        if (root == null) return;
//        dfs(root);
//    }
    TreeNode father = new TreeNode();

    public void flatten(TreeNode root) {
        if (root == null) return;
        father.left = null;
        father.right = root;
        father = root;

        TreeNode left = root.left;
        TreeNode right = root.right;
        flatten(left);
        flatten(right);
    }

    public static void main(String[] args) {
        Q0114 sl = new Q0114();
        TreeNode root = Tree.createTreeByPreorderAndInorder(new int[]{1, 2, 3}, new int[]{2, 1, 3});
        sl.flatten(root);
        Tree.preorderTraversal(root);
    }
}